package cn.wit.testalgorithms;

import java.util.Stack;

/**
 * 20.有效的括号
 * 
 * 这类问题都可以用栈处理
 * 
 * @author 16604
 *
 */
public class DemoEffictveBrackets {

	public static void main(String[] args) {

		String s = "()";

		System.out.println(isValid(s));

	}

	public static boolean isValid(String s) {

		// 先new一个栈出来
		Stack<Character> sk = new Stack<Character>();
		// stack<char> sk;

		// 遍历字符串
		for (int i = 0; i < s.length(); i++) {

			// 如果满足，就进入栈
			if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
				sk.push(s.charAt(i));
			} else {
				// 括号匹配
				if (sk.empty() || s.charAt(i) == ')' && sk.peek() != '(' || s.charAt(i) == ']' && sk.peek() != '['
						|| s.charAt(i) == '}' && sk.peek() != '{') {
					return false;
				}
				// 如果匹配，一定要输出栈顶元素

				sk.pop();

			}
		}

		return sk.empty();

	}
}
